package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode
import xyz.scootaloo.oj.ds.helper.CollectionBuilder
import java.util.*

/**
 * @author flutterdash@qq.com
 * @since 2021/4/10 22:15
 */
class P26 {

    private fun isSubStructure(A: TreeNode?, B: TreeNode?): Boolean {
        if (B == null || A == null) return false
        val stack = Stack<TreeNode>()
        stack.push(A)
        while (!stack.isEmpty()) {
            val currentNode = stack.pop()
            if (currentNode.`val` == B.`val` && check(currentNode, B))
                return true
            if (currentNode.right != null) stack.push(currentNode.right)
            if (currentNode.left != null) stack.push(currentNode.left)
        }
        return false
    }

    private fun check(root: TreeNode?, sub: TreeNode?): Boolean {
        if (sub == null) return true
        if (root == null) return false
        if (root.`val` != sub.`val`) return false
        return check(root.left, sub.left) && check(root.right, sub.right)
    }

    @Test
    fun test0() {
        val rootA = CollectionBuilder.initTree()
            .setRoot(3)
            .addLevel(4, 5)
            .addLevel(1, 2)
            .build()
        val rootB = CollectionBuilder.initTree()
            .setRoot(4)
            .addLevel(1).build()
        println(isSubStructure(rootA, rootB))
    }

}
